#[test]
fn test_exist() {
    assert!(exist(
        vec![
            vec!['A', 'B', 'C', 'E'],
            vec!['S', 'F', 'C', 'S'],
            vec!['A', 'D', 'E', 'E']
        ],
        String::from("ABCCED")
    ));

    assert!(exist(
        vec![
            vec!['A', 'B', 'C', 'E'],
            vec!['S', 'F', 'C', 'S'],
            vec!['A', 'D', 'E', 'E']
        ],
        String::from("SEE")
    ));

    assert!(!exist(
        vec![
            vec!['A', 'B', 'C', 'E'],
            vec!['S', 'F', 'C', 'S'],
            vec!['A', 'D', 'E', 'E']
        ],
        String::from("ABCB")
    ));
}

/*
79. 单词搜索
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

示例 3：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false
提示：
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成
进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？
 */
pub fn exist(board: Vec<Vec<char>>, word: String) -> bool {
    fn dfs(
        board: &Vec<Vec<char>>,
        used: &mut Vec<Vec<bool>>,
        i: usize,
        j: usize,
        chs: &[u8],
    ) -> bool {
        if chs.len() == 0 {
            return true;
        }

        if i > 0 && !used[i - 1][j] && board[i - 1][j] as u8 == chs[0] {
            //上
            used[i - 1][j] = true;
            if dfs(board.as_ref(), used.as_mut(), i - 1, j, &chs[1..]) {
                return true;
            }
            used[i - 1][j] = false;
        }
        if i < board.len() - 1 && !used[i + 1][j] && board[i + 1][j] as u8 == chs[0] {
            //下
            used[i + 1][j] = true;
            if dfs(board.as_ref(), used.as_mut(), i + 1, j, &chs[1..]) {
                return true;
            }
            used[i + 1][j] = false;
        }
        if j > 0 && !used[i][j - 1] && board[i][j - 1] as u8 == chs[0] {
            used[i][j - 1] = true;
            if dfs(board.as_ref(), used.as_mut(), i, j - 1, &chs[1..]) {
                return true;
            }
            used[i][j - 1] = false;
        }
        if j < board[0].len() - 1 && !used[i][j + 1] && board[i][j + 1] as u8 == chs[0] {
            used[i][j + 1] = true;
            if dfs(board.as_ref(), used.as_mut(), i, j + 1, &chs[1..]) {
                return true;
            }
            used[i][j + 1] = false;
        }
        false
    }

    let chs = word.as_bytes();
    let (m, n) = (board.len(), board[0].len());
    let mut used = vec![vec![false; n]; m];
    for i in 0..m {
        for j in 0..n {
            if board[i][j] as u8 == chs[0] {
                used[i][j] = true;
                if dfs(board.as_ref(), used.as_mut(), i, j, &chs[1..]) {
                    return true;
                }
                used[i][j] = false;
            }
        }
    }
    false
}
